package algorithm.dynamic;

import java.util.Arrays;

/**
 * leetcode : https://leetcode.com/problems/house-robber-ii/
 * Difficulty : Medium
 *
 * 题目是HouseRobber的升级版，与前一题的区别在于，最后一个房子和第一个是相连的，形成了一个环。
 * 那么，如果一开始抢了第一间房子，那么最后一间就不可以抢了。反之，则可以抢最后一间。
 *
 *
 * @Author Antony
 * @Since 2018/11/1 14:34
 */
public class HouseRobberII {


    /**
     * leetcode : 4ms - 82.17%
     *
     * 思路：
     * 由题意，可以分为两种情况
     * 如果抢了第一间，那么最后一间不可以抢。如果第一间不抢，那么最后一间可以抢。
     * 则可以转化为两个HouseRobber的场景
     * 然后对两种结果取Max即可。
     *
     * 注意：
     * 1）拆分的时候使用copy的方法，因为subRob方法会修改原数组的值
     * 2）注意长度为1时，直接返回
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int[] subArr1 = Arrays.copyOfRange(nums,0,nums.length-1);
        int[] subArr2 = Arrays.copyOfRange(nums,1, nums.length);
        return Math.max(subRob(subArr1), subRob(subArr2));
    }

    public static int subRob(int[] nums){
        int max=nums[0];
        int idx1,idx2, tmp1,tmp2, tmpDp;
        for(int i=1; i<nums.length; i++){
            idx1 = i-2;
            idx2 = i-3;
            tmp1 = idx1>=0 ? nums[idx1] : 0;
            tmp2 = idx2>=0 ? nums[idx2] : 0;
            tmpDp = tmp1 > tmp2 ? tmp1+nums[i] : tmp2+nums[i];
            nums[i] = tmpDp;
            max = Math.max(max, tmpDp);
        }
        return max;
    }
}
